/*
 * @lc app=leetcode.cn id=55 lang=cpp
 *
 * [55] 跳跃游戏
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    bool canJump(vector<int>& nums) {
        // DP ??

        // the max index you can reach
        int maxDis = 0;
        // now need to let maxDis >= nums.size()-1
        for (int i=0;i<=maxDis and i<nums.size()-1;i++){
            if (i + nums[i] > maxDis){
                maxDis = i + nums[i];
            }
        }
        return maxDis >= nums.size()-1;
    }
};
// @lc code=end

// [2,3,1,1,4]